% TODO png blur? too wide listings
\section{Информационная энтропия}
\label{entropy}
\myindex{Entropy}

Ради упрощения, я бы сказал, что информационная энтропия это мера, насколько хорошо можно сжать
некоторый блок данных.
Например, обычно нельзя сжать файл, который уже был сжат, так что он имеет высокую энтропию.
С другой стороны, 1MiB нулевых байт можно сжать в крохотный файл на выходе.
Действительно, в обычном русском языке, один миллион нулей можно описать просто как
``в итоговом файле 1 миллион нулевых байт''.
Сжатые файлы это обычно список инструкций для декомпрессора вроде
``выдай 1000 нулей, потом байт 0x23, потом байт 0x45, потом выдай блок длиной в 10 байт, который мы видели 500 байт назад,
итд.''

Тексты, написанные на натуральных языках, также легко могут быть сжаты, по той причине что в натуральных языках очень
много избыточности (иначе мелкая опечатка могла бы привести к непониманию, так, как любой перевернутый бит в сжатом
архиве приводит к невозможности декомпрессии),
некоторые слова используются чаще, итд.
Из обычной ежедневной речи можно выкидывать вплоть до половины слов, и всё еще можно будет что-то понять.

Код для CPU тоже может быть сжат, потому что некоторые инструкции в \ac{ISA} используются чаще других.
\myindex{x86!\Instructions!MOV}
\myindex{x86!\Instructions!PUSH}
\myindex{x86!\Instructions!CALL}
В x86 самые используемые инструкции, это \INS{MOV}/\INS{PUSH}/\INS{CALL} (\myref{correctly_disasmed_code}).

Компрессоры данных и шифры выдают результаты с очень большой энтропией.
Хорошие \ac{PRNG} также выдают данные, которые нельзя сжать
(по этому признаку можно измерять их качество).

Так что, другими словами, энтропия это мера, которая может помочь узнать содержимое неизвестного блока данных.

\input{ff/entropy/math_RU}

\subsection{Вывод}

Информационная энтропия может использоваться как простой метод для быстрого изучения неизвестных бинарных файлов.
В частности, это очень быстрый способ найти сжатые/зашифрованные фрагменты данных.
Кто-то говорит, что так же можно находить открытые/закрытые ключи \ac{RSA} (и для других несимметричных шифров)
в исполняемом коде (ключи также имеют  высокую энтропию), но я не пробовал.

\subsection{Инструменты}

Удобная утилита из Linux \IT{ent} для вычисления энтропии файла\footnote{\url{http://www.fourmilab.ch/random/}}.

Неплохой онлайновый визуализатор энтропии, сделанный Aldo Cortesi,
которому я пытался подражать при помощи Mathematica: \url{http://binvis.io}.
Его статьи о визуализации энтропии тоже стоит почитать:
\url{http://corte.si/posts/visualisation/entropy/index.html},
\url{http://corte.si/posts/visualisation/malware/index.html},
\url{http://corte.si/posts/visualisation/binvis/index.html}.

\myindex{radare2}
В фреймворке radare2 есть команда \IT{\#entropy}.

Для IDA есть IDAtropy\footnote{\url{https://github.com/danigargu/IDAtropy}}.

\subsection{Кое-что о примитивном шифровании как XOR}

Интересно, что простое шифрование при помощи XOR не меняет энтропии данных.
В этой книге я показал это в примере с \IT{Norton Guide} (\myref{norton_guide}).

Обобщая: шифрования при помощи шифровании с заменой также не меняет энтропии данных
(а XOR можно рассматривать как шифрование заменой).
Причина в том, что алгоритм вычисления энтропии рассматривает данные на уровне байт.
С другой стороны, данные зашифрованные с 2-х или 4-х байтным XOR-шаблоном приведут к другому уровню энтропии.

Так или иначе, низкая энтропия это обычно верный признак слабой любительской криптографии
(которая используется в лицензионных ключах/файлах, итд).

\subsection{Еще об энтропии исполняемого кода}

Легко заметить, что наверное самый большой источник большой энтропии в исполняемом коде это
относительные смещения закодированные в опкодах.
Например, эти две последовательные инструкции будут иметь разные относительные смещения в своих опкодах,
в то время как они, на самом деле, указывают на одну и ту же ф-цию:

\begin{lstlisting}[style=customasmx86]
function proc
...
function endp

...

CALL function
...
CALL function
\end{lstlisting}

Идеальный компрессор исполняемого кода мог бы кодировать информацию так:
\IT{есть CALL в ``function'' по адресу X и такой же CALL по адресу Y} без необходимости кодировать
адрес ф-ции \IT{function} дважды.

\myindex{UPX}
Чтобы с этим разобраться, компрессоры исполняемых файлов иногда могут уменьшить энтропию здесь.
Один из примеров это UPX: \url{http://sourceforge.net/p/upx/code/ci/default/tree/doc/filter.txt}.

\subsection{\ac{PRNG}}

\myindex{GnuPG}
Когда я запускаю GnuPG для генерации закрытого (секретного) ключа, он спрашивает об энтропии \dots

\begin{lstlisting}
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

Not enough random bytes available.  Please do some other work to give
the OS a chance to collect more entropy! (Need 169 more bytes)
\end{lstlisting}

Это означает что хороший \ac{PRNG} выдает длинные результаты с большой энтропией,
и это тоже что нужно для секретного ключа в ассиметричной криптографии.
Но \ac{CPRNG} это сложно (потому что компьютер сам по себе это очень детерменистичное устройство),
так что GnuPG просит у пользователя дополнительной случайной информации.

\subsection{Еще примеры}

Вот случай, где я делаю попытку подсчитать энтропию некоторых блоков с неизвестным содержимым: \myref{encrypted_DB1}.

\input{ff/entropy/files_RU}

\subsection{Понижение уровня энтропии}

Автор этих строк однажды видел ПО, которое хранило каждый шифрованный байт в трех байтах:
каждый имел значение {\Large $\approx \frac{byte}{3}$}, так что реконструирование шифрованного байта включало в себя
суммирование трех последовательно расположенных байт.
Выглядит абсурдно.

Но некоторые люди говорят, что это было сделано для сокрытия того самого факта, что данные имеют внутри что-то зашифрованное:
измерение энтропии такого блока покажет уровень энтропии намного ниже.

